\documentclass{beamer}
%\usepackage[latin1]{inputenc}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usetheme{Warsaw}
\title{Optimalizační algoritmus CMA-ES}
\author{Antonín Šulc}
\institute{DCE FEL CTU Prague}
\date{16. 06. 2011}
\begin{document}

\begin{frame}
\titlepage
\end{frame}


\begin{frame}{Osnova}
\begin{enumerate}
\item Cíle práce.
\item Představení algoritmu CMA-ES.
\item Varianta IPOP-CMA-ES.
\item Varianta $\sigma$-$\mathbf{m}$-IPOP-CMA-ES.
\item Porovnání s ostatními algoritmy.
\item Implementace.
\item Dosažené cíle.
\item Závěr.
\end{enumerate}
\end{frame}

\begin{frame}{Zadání práce}
\begin{enumerate}
\item Prozkoumat základní algoritmus CMA-ES.
\item Implementovat algoritmus do knihovny JCool.
\item Prozkoumat stávající implementace CMA-ES.
\item Provést sadu experimentů nad algoritmem.
\end{enumerate}
\end{frame}

\begin{frame}{Popis CMA-ES}
Algoritmus CMAES je $\left(\mu/\mu_W,\lambda\right)$-ES
\begin{enumerate}
\item V každém kroku navzorkuje $\lambda\geq 2$ jedinců $\{\mathbf{x}_1^{(g)},\mathbf{x}_2^{(g)},\dots \mathbf{x}_\lambda^{(g)} \}$ podle normálního rozdělení $\mathcal{N}\left(\mathbf{m}^{(g)},\mathbf{C}^{(g)}\right)$.
\item Vybere $\mu\leq \lambda$ lepších jedinců $\{\mathbf{x}_1^{(g)},\mathbf{x}_2^{(g)}\dots \mathbf{x}_\mu^{(g)}\}\subseteq \{\mathbf{x}_1^{(g)},\mathbf{x}_2^{(g)},\dots \mathbf{x}_\lambda^{(g)} \}$ podle jejich ohodnocení $f\left(\mathbf{x}_i^{(g)}\right)$.
\item Nad vybranou množinou jedinců spočítá novou střední hodnotu $\mathbf{m}^{(g+1)}$ a novou kovarianční matici $\mathbf{C}^{(g+1)}$ pro $\mathcal{N}\left(\mathbf{m},\mathbf{C}\right)$ v další generaci. 	 
\end{enumerate}
\end{frame}

%\begin{frame}{Výpočet CMA-ES}
%\begin{enumerate}
%\item Normální rozdělení vyžaduje symetrickou a pozitivně definitní matici $\mathbf{C}$ (rank-$\mu$-update, rank-$1$-update).
%\item Ošetření předčasné konvergence - exponenciální vyhlazování.
%\item Dostatečně velké preference lepších jedinců - $\mu_W$ selekce.
%\end{enumerate}


%\begin{equation}
%\mathbf{C}^{\left(g+1\right)}=\left(1-c\right)\mathbf{C}^{(g)}+c_1\left(1-update\right)+c_\mu\left(\mu - update \right)
%\end{equation}
%\end{frame}

\begin{frame}{Vzorkování podle $\mathcal{N}\left(\mathbf{m},\mathbf{C}\right)$}
\begin{figure}
\includegraphics[scale=0.25]{./figures/normal_distribution.png}
\caption{Vzorkování jedinců podle normálního rozdělení}
\end{figure}

\end{frame}

\begin{frame}{Kroky algoritmu CMA-ES}
\begin{figure}
\includegraphics[scale=0.4]{figures/CmuEstimation.png}
\caption{Kroky CMA-ES. $\lambda=300$ vzorků z nichž je $\mu=100$ nejlepších vybráno k výpočtu.}
\end{figure}
\end{frame}

\begin{frame}{IPOP-CMA-ES}
\begin{center}
\textbf{IPOP-CMA-ES}
\end{center}
Modifikace algoritmus CMA-ES o restart a nárůst populace.

\begin{enumerate}
\item CMA-ES může uváznout v lokálním optimu - dosáhl zastavovacích podmínek $\rightarrow$ je vhodné ho restartovat.
\item Pokud došlo k restartu, víme už aspoň o jednom optimu (nebo značné divergenci řešení), je vhodné robustnější vyhledávání $\rightarrow$ po restartu je vhodné zvětšit počet $\lambda$ o multiplikativní násobek $\Delta \lambda\geq 1$.
\end{enumerate} 		
\end{frame}

\begin{frame}{$\sigma$-$\mathbf{m}$-CMA-ES}
\begin{center}
\textbf{$\sigma$-$\mathbf{m}$-IPOP-CMA-ES}
\end{center}
Modifikace algoritmu IPOP-CMA-ES o paměť $\sigma$ a $\mathbf{m}$.
\begin{enumerate}
\item IPOP-CMA-ES po restartu ztratí veškeré informace o běhu algoritmu svým restartem $\rightarrow$ po restartu spočítáme $\sigma$ a $\mathbf{m}$ po restartu jako průměr z nejlepších a nejhorších jedinců.
\end{enumerate}

\begin{figure}
\includegraphics[scale=0.4]{figures/sigma_m_ipopcmaes.png}
\end{figure}
\end{frame}

\begin{frame}{Implementace}
\begin{itemize}
\item Každý algoritmus má svou třídu, která provádí atomické operace.
\item Důraz na snadnou rozšířitelnost. 
\item K maticovým výpočtům jsem použil knihovnu Java-Commons-Math 2.1.
\item Implementace je přibližně stejně rychlá jako implementace autora algoritmu v Matlabu.
\item Reverzně porovnáno s výpočtem od autora s implementací v Matlabu.
\item Zastavovací podmínky algoritmu jsou existují nezávisle na algoritmu. Mají své třídy.
\end{itemize}
\end{frame}
\begin{frame}{Třídy v JCool}
\begin{figure}
\includegraphics[scale=0.25]{./figures/CMAESMethodClassHierarchy.png}
\caption{Třídy zapouzdřující chování}
\end{figure}
\end{frame}

%\begin{frame}{Porování se všemi algoritmy}
%\begin{figure}
%\includegraphics[scale=0.35]{./figures/computation/10000_iterations.png}
%\caption{Porovnání algoritmů na nejlepší hodnotu v poslední generaci.}
%\end{figure}
%\end{frame}

%\begin{frame}{Porovnání Ackleyovy funkce}
%\begin{figure}
%\includegraphics[scale=0.4]{figures/AckleyBest.png}
%\caption{Nejlepší hodnoty všech metod pro Ackleyovu funkci.}
%\end{figure}
%\end{frame}

%\begin{frame}{Porovnání Rosenbrockovy funkce}
%\begin{figure}
%\includegraphics[scale=0.4]{figures/RosenbrockBest.png}
%\caption{Nejlepší hodnoty všech metod pro Rosenbrockovu funkci.}
%\end{figure}
%\end{frame}

\begin{frame}{Porovnání se všemi algoritmy}
\begin{table}
\begin{tabular}{|c|c|}
\hline
Algoritmus & Počet vítězství\\
\hline
IPOPCMAES & 6\\
\hline
HGAPSO & 6\\
\hline
PureCMAES & 5\\
\hline
AACA & 4\\
\hline
ACO & 4\\
\hline
QuasiNewton &3\\
\hline
SteepestDescent &2\\
\hline
API & 1\\
\hline
DifferentialEvolution & 1\\
\hline
\end{tabular}
\end{table}
Metody CACO, DACO, OrthogonalSearch, PALDifferentialEvolution, PBIL, Powell, PSO, Random a SADE nezvítězili ani jednou.
\end{frame}

\begin{frame}{Porovnání Levy5 funkce}
\begin{figure}
\includegraphics[scale=0.4]{figures/Levy5Best.png}
\caption{Nejlepší hodnoty všech metod pro Levyho funkci.}
\end{figure}
\end{frame}

%\begin{frame}{Kroky CMA-ES pro Ackleyovu a Rosenbrockovu funkci}
%\begin{tabular}{cc}
%\includegraphics[scale=0.3]{figures/ackley.png} & \includegraphics[scale=0.3]{figures/rosenbrock.png}
%\end{tabular}
%\end{frame}

%\begin{frame}{Kroky CMA-ES pro Rastriginovu funkci}
%\begin{figure}
%\includegraphics[scale=•]{•}=0.3]{figures/rastrigin.png}
%\end{figure}
%\end{frame}

\begin{frame}{Dosažené cíle}
\begin{enumerate}
\item Podrobně jsem prozkoumal, zanalyzoval a zdokumentoval všechny kroky algoritmu.
\item Algoritmus CMA-ES je implementován v knihovně JCool, navíc jsem implementoval IPOP-CMA-ES a svou variantu $\sigma$-$\mathbf{m}$-IPOP-CMA-ES.
\item Existující implementace jsem prozkoumal a zdokumentoval.
\item Experimentálně jsem porovnal algoritmus s ostatními a navíc jsem ověřil teoretické hypotézy z teorie  na chování algoritmu. 
\end{enumerate}
\end{frame}


\begin{frame}{Dotazy}
\begin{center}
Prostor pro dotazy.
\end{center}
\end{frame}

\begin{frame}{Závěr}
\begin{center}
Děkuji za pozornost.
\end{center}
\end{frame}

\end{document}